#!/usr/bin/python

from itertools import count
from copy import deepcopy
from collections import defaultdict
from operator import itemgetter

from tools import heap
from tools.sample import generate_weighted_edges

from itertools import product


class graph_exception(Exception):
    pass



class Graph(object):

    __dict__ = ('_vertices', '_edges')

    def __init__(self, *args):
        if args:
            self._edges = deepcopy(args[0])

            vertices = defaultdict(list)
            for u, v in self._edges.iterkeys():
                vertices[u].append(v)
            self._vertices = dict(vertices)
        else:
            self._edges, self._vertices = {}, {}

    def vertices(self):
        return self._vertices.iterkeys()

    def adjacent(self, node):
        return self._vertices[node]

    def get_weight(self, u, v):
        return self._edges.get((u, v), None)

    def __eq__(self, other):
        if isinstance(other, Graph):
            return self._vertices == other._vertices and\
                self._edges == other._edges
        else:
            return False

    def subgraph(self, L):
        def gmaker(vlist):
            edges = {}
            for u, v in product(vlist, vlist):
                weight = self._edges.get((u, v), None)
                if weight is not None:
                    edges[u, v] = weight
            return Graph(edges)
        return [gmaker(e) for e in L]


def find_path_prio(G, x, y):
    visited, fringe = {}, heap(itemgetter(1))
    fringe.push((x, 0, None))
    solution = None

    while fringe:
        node, distance, parent = fringe.top()
        fringe.pop()
        if node in visited:
            continue

        visited[node] = parent
        if node == y:
            solution = distance
            break
        else:
            for child in G.adjacent(node):
                child_distance = distance + G.get_weight(node, child)
                fringe.push((child, child_distance, node))

    if solution is None:
        return None, None
    else:
        path, node = [y], visited[y]
        while node is not None:
            path.insert(0, node)
            node = visited[node]

        return solution, path



def get_bfs_tree(g, root):
    vertices, visited, tree = [root], set((root,)), graph(graph_type.orgraph)
    tree.add_vertex(root)

    while vertices:
        v = vertices.pop(0)

        for u in g.neigbours(v):
            if u not in visited:
                vertices.append(u)
                visited.add(u)
                tree.add_vertex(u)
                tree.add_edge(v, u)
    return tree

def get_dfs_tree(g, root):
    vertices, visited, tree = [root], set((root,)), graph(graph_type.orgraph)
    tree.add_vertex(root)

    def walker():
        u = vertices.pop()
        for v in g.neigbours(u):
            if v not in visited:
                vertices.append(v)
                visited.add(v)
                tree.add_vertex(v)
                tree.add_edge(u, v)
                walker()
    walker()
    return tree


def find_path(g, x, y):
    parents, visited, queue = {}, set((x,)), [x]

    while queue:
        u = queue.pop(0)
        for v in g.neigbours(u):
            if v not in visited:
                queue.append(v)
                visited.add(v)
                parents[v] = u

    def pathfinder(ps, x, y):
        path, item = [y], parents[y]
        while item != x:
            path.append(item)
            item = parents[item]
        path.append(x)
        path.reverse()
        return path
    return pathfinder(parents, x, y)


def sorting(g):
    '''Does the topological sorting of the graph g.'''


def find_components(g):
    '''Find linked components of the graph.'''
    visited, components = set(), []

    def visit(root, component):
        if root not in visited:
            visited.add(root)
            component.append(root)
            for child in g.adjacent(root):
                visit(child, component)

    for v in g.vertices():
        component = []
        if v not in visited:
            visit(v, component)
            components.append(component)

    return g.subgraph(components)

def find_articulation_vertices(g):
    '''Finds articulation vertices of the graph g.'''
    numbers = {}

    numerator, apoints = count(), []

    def root_handler(root):
        root_number = numbers[root] = next(numerator)
        children_count = 0
        for child in g.neigbours(root):
            if child in numbers:
                children_count += 1
            node_handler(child)
        if children_count > 1:
            apoints.append(root)

    def node_handler(node):
        node_number = numbers[node] = next(numerator)
        is_articulation, reachable_from = False, 100000000

        for child in g.neigbours(node):
            child_number = numbers.get(child, None)
            if child_number is None:
                child_reachable_from = node_handler(child)
                if child_reachable_from == node_number:
                    is_articulation = True
                reachable_from = min(reachable_from, child_reachable_from)
            else:
                reachable_from = min(reachable_from, child_number)
        if is_articulation:
            apoints.append(node)
        return reachable_from

    root_handler(g.keys()[0])
    return apoints

def find_cycles(G):
    '''Find euler cycles in the graph G.'''
    visited = set()

    def handle_node(node, parent):
        visited.add(node)
        cycles = {}
        for child in G.neigbours(node):
            if child not in visited:
                for key, value in handle_node(child, node).iteritems():
                    value.append(node)
                    cycles[key] = value
            elif child is parent:
                pass
            else:
                cycles[child] = [child, node]
        return cycles

    root = G.keys()[0]
    visited.add(root)
    cycles = {}
    for child in G.neigbours(root):
        cycles.update(handle_node(child, root))

    return cycles

if __name__ == '__main__':

    def test_1():
        g = graph()
        g.add_vertex((1, 2, 3, 4))

        g.add_edge(1, 2)
        g.add_edge(1, 3)
        g.add_edge(2, 3)
        g.add_edge(2, 4)
        g.add_edge(3, 4)

        g.add_vertex(5)
        g.add_vertex(6)
        g.add_edge(5, 6)

        #print get_bfs_tree(g, 1)
        #print get_dfs_tree(g, 1)
        print find_path(g, 5, 4)

    def test_2():
        g = graph(graph_type.graph)
        with open('tri.g') as fd:
            g.load(fd)
        print find_articulation_vertices(g)
